1. Field of the Invention
Methods and apparatuses consistent with the present invention relate to encoding of video data, and more particularly, to a method of and an apparatus for deciding an encoding mode for variable block size motion estimation, which can decide an encoding mode quickly and with less computation during variable block size motion estimation.
2. Description of the Related Art
In video compression standards such as moving picture expert group (MPEG)-1, MPEG-2, MPEG-4 Visual, H.261, H.263, and H.264/MPEG-4 advanced video coding (AVC), a frame is generally divided into a plurality of macroblocks. Next, prediction is performed on each of the macroblocks to obtain a prediction block, and the difference between the original block and the prediction block is transformed and quantized for video data compression.
There are two types of prediction: intraprediction and interprediction. In intraprediction, a current block is predicted using data of its neighboring blocks in the current frame. In interprediction, a prediction block of the current block is generated from one or more video frames that have been encoded using block-based motion compensation. H.264/MPEG-4 AVC uses interprediction to perform motion estimation using seven variable block size modes from 4×4 to 16×16, instead of a fixed block size mode.
FIG. 1 illustrates blocks of various sizes used in variable block size motion estimation of related art H.264/MPEG-4 AVC, and FIG. 2 illustrates a variable block size motion estimated image according to the related art.
As illustrated in FIG. 1, a luminance component (16×16 sample) of a macroblock may be divided according to four methods: into one 16×16 macroblock partition, two 16×8 macroblock partitions, two 8×16 macroblock partitions, or four 8×8 macroblock partitions for motion estimation. If an 8×8 mode is selected, four 8×8 sub-macroblocks of a macroblock may each be sub-divided according to four methods: into one 8×8 sub-macroblock partition, two 8×4 sub-macroblock partitions, two 4×8 sub-macroblock partitions, or four 4×4 sub-macroblock partitions. In each macroblock, a large number of combinations of partitions and sub-macroblocks are available. A method of dividing a macroblock into sub-blocks of various sizes is called tree structured motion compensation.
Referring to FIG. 2, in an image, a block having low energy is motion estimated using a large partition and a block having high energy is motion estimated using a small partition. Selecting a large partition (of 16×16, 16×8, or 8×16) means that the number of bits required to indicate the motion vector and type of the selected partition is small, but motion compensated error data of a frame region including a fine image may include a large amount of energy. If a small partition (of 8×4 or 4×4) is selected, the motion compensated error data has a small amount of energy, but a large number of bits are required to indicate the motion vector and type of the selected partition. Thus, the selection of the partition size has a great influence on compression performance.
To decide the optimal encoding mode for a macroblock, H.264 uses rate-distortion (RD) optimization. A general equation for RD optimization is as follows:Jmode=D+λmode·R  (1),
where Jmode is an RD cost, λmode is a Lagrangian multiplier, D is a distortion value between the original macroblock and a reconstructed macroblock, and R is a coefficient reflecting the number of bits related to mode selection and a quantization value of a macroblock. A macroblock is divided into various variable blocks and encoded, and the mode having the minimum RD cost is selected as the optimal encoding mode using Equation 1.
However, all modes of motion estimation must be tried to select the optimal encoding mode, which increases the amount and complexity of computation. Therefore, there is a need for an encoding mode decision method capable of reducing the complexity of computation and thus rapidly and accurately deciding an encoding mode.